#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 1e6 + 5;

int n, m;
int a[N];
int lc[N], rc[N], dis[N];
struct Segment {
  int rt;
  int r;
  int sz;
} st[N];
int top;
int merge(int x, int y) {
  if (!x || !y) return x + y;
  if (a[x] < a[y]) swap(x, y);
  rc[x] = merge(rc[x], y);
  if (dis[lc[x]] < dis[rc[x]]) swap(lc[x], rc[x]);
  dis[x] = dis[rc[x]] + 1;
  return x;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  rep(i, 1, n) cin >> a[i];
  rep(i, 1, n) a[i] -= i;
  dis[0] = -1;
  rep(i, 1, n) {
    Segment now{i, i, 1};
    st[++top] = now;
    while (top > 1 && a[st[top].rt] < a[st[top - 1].rt]) {
      int x = merge(st[top].rt, st[top - 1].rt);
      --top;
      st[top].r = i;
      st[top].sz += st[top + 1].sz;
      int len = i - st[top - 1].r;
      while (st[top].sz > len / 2 + 1) {
        x = merge(lc[x], rc[x]);
        st[top].sz--;
      }
      st[top].rt = x;
    }
  }
  ll sum = 0;
  rep(i, 1, top) {
    int l = st[i - 1].r + 1;
    int r = st[i].r;
    int x = a[st[i].rt];
    rep(j, l, r) sum += abs(a[j] - x);
  }
  cout << sum << endl;
  rep(i, 1, top) {
    int l = st[i - 1].r + 1;
    int r = st[i].r;
    int x = a[st[i].rt];
    rep(j, l, r) cout << x + j << ' ';
  }
  return 0;
}